/// @tags: Binom Mobius
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int const N = 11 + 1, M = 1e5 + 1, C = 20 + 1, mod = 10007, inv = 5004;

int T, n, c, cnt, mn, ans;
bool vis[M];
int pri[M], mu[M];
int m[N];
int binom[M][C], s[M][C][N], qpow[M][N], f[N], g[M][C];

inline void prework() {
  mu[1] = 1;
  for (int i = 2; i < M; ++i) {
    if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
    for (int j = 1; j <= cnt && i * pri[j] < M; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
      mu[i * pri[j]] = -mu[i];
    }
  }
  for (int i = 0; i < M; ++i) {
    binom[i][0] = 1;
    for (int j = 1; j <= i && j < C; ++j)
      binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod;
  }
}

inline int main() {
  prework();
  for (int i = 1; i < M; ++i)
    for (int k = 0, tmp = 1; k < N; ++k, tmp = tmp * i % mod) qpow[i][k] = tmp;
  for (int j = 0; j < C; ++j)
    for (int d = 1; d < M; ++d)
      if (mu[d])
        for (int D = d; D < M; D += d) g[D][j] = g[D][j] + mu[d] * binom[D / d - 1][j];
  for (int i = 1; i < M; ++i)
    for (int j = 0; j < C; ++j) {
      if (g[i][j] >= mod) g[i][j] -= mod;
      if (g[i][j] < 0) g[i][j] += mod;
      for (int k = 0; k < N; ++k)
        if ((s[i][j][k] = s[i - 1][j][k] + g[i][j] * qpow[i][k] % mod) >= mod)
          s[i][j][k] -= mod;
    }
  cin >> T;
  while (T--) {
    cin >> n >> c;
    mn = M, ans = 0;
    for (int i = 1; i <= n; ++i) cin >> m[i], mn = min(mn, m[i]);
    for (int l = 1, r; l <= mn; l = r + 1) {
      r = mn;
      for (int j = 1; j <= n; ++j) r = min(r, m[j] / (m[j] / l));
      int tmp = 1;
      for (int j = 1; j <= n; ++j) tmp = tmp * (m[j] / l) % mod * inv % mod;
      memset(f, 0, sizeof(f)), f[0] = 1;
      for (int j = 1; j <= n; ++j) {
        for (int k = j; k > 0; --k)
          f[k] = (f[k] * m[j] * 2 % mod - f[k - 1] * (m[j] / l + 1)) % mod;
        f[0] = f[0] * m[j] * 2 % mod;
      }
      for (int j = 0; j <= n; ++j)
        ans = (ans + tmp * f[j] % mod * (s[r][c - 2][j] - s[l - 1][c - 2][j])) % mod;
    }
    cout << ((ans < 0) ? mod + ans : ans) << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4152 [WC2014] 时空穿梭.in", "r", stdin);
  freopen("P4152 [WC2014] 时空穿梭.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
